package com.zhugang.week08;

/**
 * @program algorithms
 * @description: match
 * @author: chanzhugang
 * @create: 2022/08/03 23:47
 */
public class Match {

    /**
     * 正则匹配
     *
     * @param text
     * @param pattern
     * @return
     */
    private boolean matched = false;

    public boolean match(char[] text, char[] pattern) {
        backstrack(text, pattern, 0, 0);
        return matched;
    }

    /**
     * @param text
     * @param pattern
     * @param ti
     * @param pj      相当于阶段
     */
    private void backstrack(char[] text, char[] pattern, int ti, int pj) {
        // 结束条件
        if (pj == pattern.length) {
            // 正则到结尾了
            if (ti == text.length) {
                // 可行解
                matched = true;
            }
            return;
        }

        // 做选择
        if (pattern[pj] == '*') {
            for (int k = 0; k <= text.length - ti; k++) {
                // * 匹配任意个字符
                backstrack(text, pattern, ti + k, pj + 1);
            }
        } else if (pattern[pj] == '?') {
            // ? 匹配0个或1个字符
            backstrack(text, pattern, ti, pj + 1);
            if (ti < text.length) {
                backstrack(text, pattern, ti + 1, pj + 1);
            }
        } else if (ti < text.length && pattern[pj] == text[ti]) {
            // 纯字符才能匹配
            backstrack(text, pattern, ti + 1, pj + 1);
        }
    }

}